The invention relates to a method for securely encrypting or decrypting a message or for generating or verifying a digital signature of a message, wherein a mathematical operation is applied to the message with the aid of a processor using a key, which can be represented as a binary number with a sequence of bits.
Asymmetrical cryptography systems ensure a high level of security by setting up key pairs made up of a private and public key, so that it is almost impossible for an attacker to decrypt the private key or the message encrypted with the public key in finite time. Standard cryptography systems, like those based on elliptic curves, are based on an encryption that can be carried out in polynomial time, but can only be inverted in bits in exponential time relative to the length of the key. In the case of systems based on elliptic curves, key lengths of n=160 to 192 bits are currently used, in the case of systems based on RSA algorithms, lengths of n=1024 to 1536 bits have to be used for a roughly identical level of security.
An alternative to the attack methods based on encryption inversion, which themselves also comprise algorithms to crack the algorithm underlying the encryption as efficiently as possible, is what are known as side-channel attacks. These can be used in particular with mobile aids, such as smart cards or dongles, on which secret key material is stored to allow an encrypted exchange of messages or to generate digital signatures or to re-encrypt.
The attacker uses the comparatively easy accessibility of data lines of the corresponding circuits to measure physical variables, such as power, electromagnetic radiation, results in the event of induced errors or propagation times of specific calculations. By directly evaluating measured values based on a simple power analysis (SPA) or by recording measured values such as power using a storage oscilloscope and then evaluating them statistically it is possible to obtain information about the underlying algorithm or even simply just about a currently existing key in an efficient manner.
The latter will be explained in more detail using an example: an encryption method provides for the application of a mathematical operation both for algorithms based on elliptic curves and for those based on the RSA method. In the case of the RSA method a modular exponentiationz=ak mod N has to be carried out, where the module N and a are natural numbers and k is a key (private or public) or at least a variable derived therefrom. In the case of elliptic curves a scalar multiplicationQ=k*P has to be carried out as the mathematical operation, where P is a point on an elliptic curve over a finite field K and k again is a key or a variable derived therefrom.
An elliptic curve is a zero set of a quadratic equationy2+a1xy+a3y=x3+a2x2+a4x+a6,with coefficients ai in a finite field. The elliptic curve has no singular points and, when an infinitely distant point is added as a neutral element, forms an additive group, whose group law can be interpreted geometrically. Each straight line intersects an elliptic curve at three not necessarily different points and a third point can be calculated for every two points, so that the sum of the three points is the neutral element. The addition is carried out (geometrically speaking) by plotting a straight line through two points P and Q, determining the third point S intersecting the elliptic curve and mirroring the point at the x-axis. Scalar multiplication of a point with a scalar k is enabled by k-times addition of a point to itself.
Cryptosystems based on elliptic curves have been known since 1985 (introduced by Koblitz, N. and Miller, V.). This and the older RSA method (Rivest, R., Shamir, A., Adleman, L.) are described in detail for example in Menezes, van Oorschot, Vanstone “Handbook of Applied Cryptography”, CRC Press (1996). In contrast to elliptic curves, in RSA systems calculations are carried out in multiplicative semigroups. The analogy of the addition according to the elliptic curve is the multiplication in the RSA system. An exponentiation results from the scalar multiplication here.
Returning to the explanatory example, it can be established that a computational conversion of the mathematical operation can take place by the following algorithm, where k is predefined by a binary representation (bi, i=n−1 . . . 0):
      Algorithm    ⁢                  ⁢    1    ⁢    a    ⁢          :        ⁢                  ⁢          (                        RSA          ⁢                      :                    ⁢                                          ⁢          z                =                              a            k                    ⁢                                          ⁢                      mod                    ⁢                                          ⁢          N                    )                          (        1        )            ⁢                          ⁢      z        ←    1                      (        2        )            ⁢                          ⁢      i        ←          n      -      1                          (        3        )            ⁢                          ⁢      while      ⁢                          ⁢      i        >          -      1                                                (            3.1            )                    ⁢                                          ⁢          z                ←                              z            2                    ⁢                                          ⁢                      mod                    ⁢                                          ⁢                      N            ⁢                                                  (            3.2            )                    ⁢                                          ⁢          if          ⁢                                          ⁢                      b            i                              =      1        ,                  then        ⁢                                  ⁢        z            ←                        z          *                ⁢        a        ⁢                                  ⁢                  mod                ⁢                                  ⁢                  N          ⁢                                          (          3.3          )                ⁢                                  ⁢        i            ←              i        -        1                        (      4      )        ⁢                  ⁢    return    ⁢                  ⁢    z        Algorithm    ⁢                  ⁢    1    ⁢    b    ⁢          :        ⁢                  ⁢          (                        EC          -                      elliptic            ⁢                                                  ⁢            curve            ⁢                          :                        ⁢                                                  ⁢            Q                          =                  k          *          P                    )                          (        1        )            ⁢                          ⁢      Q        ←    0                      (        2        )            ⁢                          ⁢      i        ←          n      -      1                          (        3        )            ⁢                          ⁢      while      ⁢                          ⁢      i        >          -      1                                    (          3.1          )                ⁢                                  ⁢        Q            ←              2        *                  Q          ⁢                                          (          3.2          )                ⁢                                  ⁢        if        ⁢                                  ⁢                  b          i                      =                  1        ⁢                                  ⁢        then        ⁢                                  ⁢        Q            ←              Q        +                              P            ⁢                                                  (            3.3            )                    ⁢                                          ⁢          i                    ←              i        -        1                        (      4      )        ⁢                  ⁢    return    ⁢                  ⁢    Q  
Therefore essentially two computation operations respectively are carried out in each loop, a so-called square-and-multiply with the RSA system and a so-called double-and-add with the EC system (EC will be used hereafter as an abbreviation of elliptic curves).
In the case of a simple power analysis (SPA) the power consumption profile of an exponentiation or scalar multiplication is analyzed. The scalar multiplication for example primarily includes additions and doubling operations. The operations differ substantially in the number of elementary operations in K, so that the power consumption is also different. It is therefore possible to draw conclusions about the individual bits and therefore the binary representation of k by a corresponding side-channel attack.
A first step in defending against such attacks is matching the power flows and computation propagation times that are a function of a respective bit for the two possible bits states 0 and 1, as shown below:
      Algorithm    ⁢                  ⁢    2    ⁢    a    ⁢          :        ⁢                  ⁢          (                        RSA          ⁢                      :                    ⁢                                          ⁢          z                =                              a            k                    ⁢                                          ⁢                      mod                    ⁢                                          ⁢          N                    )                          (        1        )            ⁢                          ⁢              z        0              ←    1                      (        2        )            ⁢                          ⁢      i        ←          n      -      1                          (        3        )            ⁢                          ⁢      while      ⁢                          ⁢      i        >          -      1                                    (          3.1          )                ⁢                                  ⁢                  z          0                    ←                        z          0          2                ⁢                                  ⁢                  mod                ⁢                                  ⁢                  N          ⁢                                          (          3.2          )                ⁢                                  ⁢                  z          1                    ←                        z          0                *        a        ⁢                                  ⁢                  mod                ⁢                                  ⁢                  N          ⁢                                          (          3.3          )                ⁢                                  ⁢                  z          0                    ←                        z          bi                ⁢                                  ⁢        with        ⁢                                  ⁢                  b          i                      =          0      ⁢                          ⁢      or      ⁢                          ⁢      1                          (        3.4        )            ⁢                          ⁢      i        ←          i      -      1                  (      4      )        ⁢                  ⁢    return    ⁢                  ⁢          z      0            Algorithm    ⁢                  ⁢    2    ⁢    b    ⁢          :        ⁢                  ⁢          (                        EC          -                      elliptic            ⁢                                                  ⁢            curve            ⁢                          :                        ⁢                                                  ⁢            Q                          =                  k          *          P                    )                          (        1        )            ⁢                          ⁢              Q        0              ←    0                      (        2        )            ⁢                          ⁢      i        ←          n      -      1                          (        3        )            ⁢                          ⁢      while      ⁢                          ⁢      i        >          -      1                                    (          3.1          )                ⁢                                  ⁢                  Q          0                    ←              2        *                              Q            0                    ⁢                                          (          3.2          )                ⁢                                  ⁢                  Q          1                    ←                        Q          0                +                              P            ⁢                                                  (            3.3            )                    ⁢                                          ⁢                      Q            0                              ←                        Q          bi                ⁢                                  ⁢        with        ⁢                                  ⁢                  b          i                      =          0      ⁢                          ⁢      or      ⁢                          ⁢      1                          (        3.4        )            ⁢                          ⁢      i        ←          i      -      1                  (      4      )        ⁢                  ⁢    return    ⁢                  ⁢          Q      0      
The first computation operation (step 3.1) and also the second computation operation (step 3.2) are now executed in each instance independently of the value of the respective bit bi. Nevertheless the propagation time increases not insignificantly here because more operations have to be carried out.
The value of the bit itself is only included in the allocation in step (3.3). If bi=0, the point Q0 (case EC) is only updated by itself in this loop. In other words: the value calculated in step (3.2) for Q1 is not taken into account, it was calculated “in vain” in the sense of the utilization of its result. If however bi=1, Q0 is allocated the value Q1. Based on the now two auxiliary variables Q0, Q1 a match is now achieved at least in power consumption and computation time in any instance as a result.
However this is not complete, as has been shown. Step (3.3) implies, as does an if/else query, a jump to addresses. Depending on the address a different power consumption can be perceived here too, so that a side-channel attack becomes possible.
An alternative method for defending against side-channel attacks is the so-called Montgomery ladder. This algorithm is particularly efficient in the case of elliptic curves but an application for RSA systems is also known from DE 10151129. When calculating the scalar multiplication it is not necessary to include the y-coordinate, if the product of the point on the elliptic curve and a factor k and at the same time a factor k+1 is calculated respectively. The y-coordinate can be reconstructed from two partial results in the case of elliptic curves.
The calculation of both results of the multiplications at the same time is advantageously integrated in a common system according to the algorithm, with the auxiliary variables defined for said purpose (R and S here) being updated efficiently with mutual assistance in each loop:
      Algorithm    ⁢                  ⁢    3    ⁢          :        ⁢                  ⁢          (                        EC          -                      elliptic            ⁢                                                  ⁢            curve            ⁢                          :                        ⁢                                                  ⁢            Q                          =                  k          *          P                    )            Montgomery    ⁢                  ⁢    ladder    ⁢          :                                    (          1          )                ⁢                                  ⁢        R            ←      P        ,          S      ←      0                          (        2        )            ⁢                          ⁢      i        ←          n      -      1                          (        3        )            ⁢                          ⁢      while      ⁢                          ⁢      i        >          -      1                          (        3.1        )            ⁢                          ⁢      if      ⁢                          ⁢              b        i              =          1      ⁢              {                              S            ←                          S              +              R                                ,                      R            ←                          2              *              R                                      }                        (      3.2      )        ⁢                  ⁢    else    ⁢                  ⁢          {                        R          ←                      R            +            S                          ,                  S          ←                      2            *            S                              }                          (        3.3        )            ⁢                          ⁢      i        ←          i      -      1                          (        4        )            ⁢                          ⁢      return      ⁢                          ⁢      R        ,                  S        ⁢                                  (        5        )            ⁢                          ⁢      reconstruct      ⁢                          ⁢      k      *      P      ⁢                          ⁢      from      ⁢                          ⁢      the      ⁢                          ⁢      points      ⁢                          ⁢      R        ,          S      ⁢                          ⁢      and      ⁢                          ⁢      P      
In the example shown in each loop the auxiliary variable R or the point R is 1*P ahead of the auxiliary variable or point S. P was predefined. For k=(1010)=10 for example S=10*P and R=11*P. The addition and doubling operation proceed in a completely uniform manner and independently of the bit. No conclusions about the bit sequence can be drawn from the sequence of operations. However the go-to instruction (“if” or “else”) is a vulnerable point for an attack, as mentioned above.